//
// Created by Zxy on 2020/8/16.
//

#ifndef QUICK_SORT_QUICKSORT_THREEWAYS_H
#define QUICK_SORT_QUICKSORT_THREEWAYS_H
#include <iostream>
#include <cassert>
#include <ctime>

// 三路快速排序处理arr[l...r]
// 将arr[l...r]分为<v,==v,>v三部分
// 之后递归<v,>v两部分继续进行三路快排
template <typename T>
void __quickSort3(T arr[], int l, int r){
    if(l >= r) return;
    swap(arr[l], arr[rand() % (r - l +1 ) + l]);
    T v = arr[l];
    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l + 1;    // arr[lt+1...i) == v
    while(i < gt){
        if(arr[i] < v){
            swap( arr[i], arr[lt+1]);
            i++;
            lt++;
        }
        else if(arr[i] > v){
            swap( arr[i], arr[gt-1]);
            gt--;
        }
        else i++; // arr[i] == v
    }
    swap( arr[l] , arr[lt] );
    __quickSort3(arr, l, lt-1);
    __quickSort3(arr, gt, r);
}

template <typename T>
void quickSort3(T arr[], int n){
    srand(time(NULL));
    __quickSort3( arr, 0, n-1);
}
#endif //QUICK_SORT_QUICKSORT_THREEWAYS_H
